A Viterbi computation is performed, for example, to decode an incoming sequence of symbols in reference to a predetermined set of symbols. See, for example, U.S. Pat. Nos. 5,502,736, 5,509,020, 5,504,784, 5,539,757 and 5,491,705.
In the Viterbi computation, the following two equations are used to compute new variable values
pk{n+1} and pl{n+1} from previous variable values pi{n} and pj{n} using constants ri and rj, as follows: EQU pk{n+1}=min(pi{n}+ri, pj{n}+rj) EQ1 EQU pl{n+1}=min(pi{n}+rj, pj{n}+ri) EQ2
Equations EQ1 and EQ2 can be represented in a diagram (FIG. 1) known as the "butterfly diagram". As seen from the above formulae, each of equations EQ1 and EQ2 requires the following steps: two additions, one comparison and one selection. Moreover, the variable values pi{n} and pj{n}, and constant values ri and rj need to be loaded from memory, and the two results pk{n+1} and pl{n+1} need to be stored back into memory. Therefore, a total of 14 steps (eight steps for equations EQ1-EQ2, and six steps for accessing memory) are needed to implement the butterfly diagram of FIG. 1. Current digital signal processors (DSPs) implement the butterfly diagram (FIG. 1) in four or more clock cycles.